//通过暴力枚举的方法来检验答案是否正确
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 用于 INT_MAX
#include <iostream>
#include <fstream>

using namespace std;

int a[100][100];
int b[100][100];
int used[100]; // 只需要一个一维数组来跟踪列的使用情况
int mini = INT_MAX; // 初始化为最大整数，用于存储最小和

void search(int a[100][100], int i, int sum, int used[], int m, int n)
{
    // 基本情况：当处理完所有行时，更新最小值
    if (i == m)
    {
        if (sum < mini)
        {
            mini = sum;
        }
        return;
    }

    // 尝试选择当前行的两个不同列的元素
    for (int s = 0; s < n; s++)
    {
        if (used[s]) continue; // 如果列 s 已被使用，则跳过
        for (int t = s + 1; t < n; t++)
        {
            if (used[t]) continue; // 如果列 t 也已被使用，则跳过
            // 标记列 s 和 t 为已使用
            used[s] = 1;
            used[t] = 1;
            // 递归调用下一行，并传递当前的和与已使用的列信息
            search(a, i + 1, sum + a[i][s] + a[i][t], used,m,n);
            // 回溯：标记列 s 和 t 为未使用，以便尝试其他组合
            used[s] = 0;
            used[t] = 0;
        }
    }
}

int main()
{
    ifstream inputDissatisfaction("../generate_samples/dissatisfaction_matrix.txt");

    int m, n;
    inputDissatisfaction >> m >> n; //读取员工数和任务数量

    // 读取5x10矩阵的元素
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            inputDissatisfaction >> a[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            b[i][j] = a[j][i];
        }
    }

    // 初始化used数组为0，表示所有列都未被使用
    for (int j = 0; j < m; j++)
    {
        used[j] = 0;
    }

    // 从第一行开始搜索，初始总和为0
    search(b, 0, 0, used,n,m);
    float a;
    a = mini;
    // 输出找到的最小和
    cout << a <<endl;

    system("pause");    //防止终端窗口运行完直接跳掉
    return 0;
}